import 'dart:collection';

import 'package:wangziyi_app/entity/citys.dart';
//


   class  SearchBinaryTree {
  //根节点
 TreeNode root;
  TreeNode put( data) {
    if (root == null) {
      TreeNode node = new TreeNode();
      node.put(data);
      root = node;
      return node;
    }
    TreeNode parent = null;
    TreeNode node = root;
    //找到要放入的位置
    while (node != null) {
      parent = node;
      if (data <= node.data) {
        node = node.leftChild;
      } else if (data >= node.data) {
        node = node.rightChild;
      } else { //是重复值 就不理会了
        return node;
      }
    }
    //生成一个节点放入
    TreeNode newNode = new TreeNode();
    newNode.put(data);
    if (data < parent.data) {
      parent.leftChild = newNode;
    } else {
      parent.rightChild = newNode;
    }
    newNode.parent = parent;

    return newNode;
  }

 /**
  * 中序遍历
  */
  midOrderTraverse(TreeNode root){
   if(root==null){
     return;
   }
   //LDR
   midOrderTraverse(root.leftChild);
   print(root.data);
   midOrderTraverse(root.rightChild);
 }
}
class TreeNode<T>{

  T data;//根节点
  TreeNode leftChild;//左子树
  TreeNode rightChild; //右子树
  TreeNode parent;//父树

 void put(T data){
    this.data=data;

  }

  }

